package 排序;

/**
 * @Author Weton Li
 * @Date 2021/3/20 12:25
 */
public class 快排 {

    public static void qSort(int[] nums, int start, int end) {

        if (start >= end) return;

        int index = partition(nums, start, end);

        qSort(nums, start, index - 1);
        qSort(nums, index + 1, end);

    }


    public static int partition(int[] nums, int start, int end) {

        int pivot = nums[start];

        int left = start, right = end; // 开始和结束的位置

        while (left < right) {

            // 从最右边向左寻找比pivot大的数，每符合一步右指针左移。当找到比pivot小的数，右指针暂时停止向左移动
            while (left < right && nums[right] >= pivot) {
                right--;
            }

            nums[left] = nums[right]; // 将当前右指针所指位置的元素 赋值给左指针指向的位置

            // 对称
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];

        }

        nums[left] = pivot;

        return left;
    }

    public static void main(String[] args) {

        int[] nums1 = {1, 5, 44, 3, 22, 55, 111, 4, 3};
        int[] nums = {1, 5, 4, 7, 3, 2};
        int[] sample = {1, 6, 55, 3, 1, 7};
//        qSort(nums, 0, nums.length - 1);
        quickSort(nums, 0, nums.length - 1);

        for (int num : nums) {
            System.out.print(num + "\t");
        }

        System.out.println("sampleQuickSort():");
        System.out.println(sample);
    }

    public static void quickSort(int[] nums, int start, int end) {

        if (start > end) {
            return;
        }

        int index = partition1(nums, start, end);

        quickSort(nums, index + 1, end);
        quickSort(nums, start, index - 1);

    }

    private static int partition1(int[] nums, int start, int end) {

        int left = start;
        int right = end;

        int pivot = nums[start]; // 基准数

        while (left < right) {

            while (left < right && nums[right] >= pivot) { // pivot右边的数必须比pivot大，否则即找到比pivot小的最新数
                right--; // // 从最右边向左寻找比pivot大的数，每符合一步右指针左移。当找到比pivot小的数，右指针暂时停止向左移动
            }
            nums[left] = nums[right]; // 将在右边找到的比pivot小的数 替换到左边

            while (left < right && nums[left] <= pivot) { // pivot左边的数必须比pivot小
                left++;
            }
            nums[right] = nums[left]; // 对称

        }
        nums[left] = pivot; // 此时left++后，新的left值赋值给了right,此时旧的left值应该被剩余的pivot所赋。
        return left;

    }

}
